function T = euclid(r)

    global t m t
    % Syndrome calculation
    S = zeros(1,2*t);
    for i  = 1 : 2*t

        S(i) = polyPlugIn(r,i);

    end

    % Euclid's algorithm
    % Init
    kk = 1;
    stopiter = 0;
    r0 = [-1*ones(1,2*t+1) 0] ; %r0 = x^(2t+1)
    r1 = [0 S];          %r1 = 1 + S(z)
    t0 = -1;
    t1 = 0;

    while kk > 0
        %calculate r0 / r1 = q_next + remainder r_next
        [q_next r_next] = polyDiv(r0,r1);
        %calculate t_next = t0 - q_next*t1
        x = polyMult(q_next,t1);
        t_next = polyAdd(t0,x);

        %update stopping condition: deg of r_next <= deg of t_next
        r_next = polyTrimZeros(r_next);
        t_next = polyTrimZeros(t_next);

        if (length(r_next) <= length(t_next))
            stopiter = 1;
        end

        %Update indices: r0->r1, r1->rnext, t0->t1, t1->t_next
        r0 = r1;
        r1 = r_next;
        t0 = t1;
        t1 = t_next;

        %Check to see if stop condition has been reached
        if stopiter == 1
            kk = 0;
        end
    end
   
    t1
    
    % Check to see if no errors are present
    if (t1(end) == 0 & t1(1:end-1) == -1*ones(size(t1(1:end-1))))
        T = r;
        return;
    end
    
    % Find the roots of t1
    rts = findRoots(t1);
    
    % Calculate the inverses of the roots of t1.  These are the error
    % locations.
    rts_inv = zeros(1,length(rts));
    for i = 1 : length(rts)
        if (~isZero(rts(i)))
        rts_inv(i) = elementDiv(0,rts(i));
        end
    end
    
    % Use Forney's Algorithm to calculate the error magnitudes
    weights = zeros(1,length(rts_inv));
    
    length(rts_inv);
    
    for i = 1 : length(rts)

        weights(i) = forney(rts, rts_inv, i, r1, t1, length(rts_inv));
%         weights(i) = forney(rts_inv, rts, i, r1, length(rts_inv));
        
    end
    
    % Now that we know the error locations and magnitudes, generate the
    % error polynomial
    err_poly = -1;
    for i = 1 : length(rts)
        term = [-1*ones(1,rts_inv(i)) weights(i)];
        err_poly = polyAdd(err_poly,term);
    end
    
	% Add the error polynomial to the received word to get the transmitted
	% code word
    T = polyAdd(err_poly,r)
    fprintf('err_poly: ');
    printPoly(err_poly);
    fprintf('Corrected Code Word:   ');
    printPoly(T)
    
end
